package com.cctc.juc.source.Bitc.Ecas.longadder;

import java.util.concurrent.ThreadLocalRandom;
import java.util.function.LongBinaryOperator;

/**
 * [分散竞争热点] 抽象（基）类。
 * 概述：[分散竞争热点] 在竞争激烈的场景下，我们可以将 AtomicLong.value 值分散到一个 Cell 数组中，不同的线程会命中到 Cell 数组的不同槽（Cell 单元格）中，各个线程只对自己槽中的 Cell.value 值进行 CAS 操作，如果要获得完整的 value 值，只需要将各个槽中的变量值（Cell.value）累加起来，返回最终的累加结果即可。
 * 这样一来，热点就被分散了，冲突的概率就小了很多。
 */
abstract class AStriped64_AAAAA extends Number {
    private static final long serialVersionUID = -7440576608206941114L;

    /**
     * [Cell 单元格]
     * [分散竞争热点] 在竞争激烈的场景下，我们可以将 AtomicLong.value 值分散到一个 Cell 数组中，不同的线程会命中到 Cell 数组的不同槽（Cell 单元格）中，各个线程只对自己槽中的 Cell.value 值进行 CAS 操作，如果要获得完整的 value 值，只需要将各个槽中的变量值（Cell.value）累加起来，返回最终的累加结果即可。
     * 这样一来，热点就被分散了，冲突的概率就小了很多。
     */
    static final class Cell {
        volatile long value;

        Cell(long x) {
            this.value = x;
        }

        final boolean cas(long expect, long update) {
            return UNSAFE.compareAndSwapObject(this, valueOffset, expect, update);
        }

    }

    // --- [核心属性] --- //

    /**
     * 基础值：
     * 1. 在没有锁竞争的情况下会直接更新这个值；
     * 2. 在 cells 初始化时，cells 不可用，也会尝试通过 CAS 操作值累加到基础值上。
     */
    transient volatile long base;
    /**
     * 热点分散值，存放 Cell 单元格的哈希表，大小为 2 的幂。
     * - 在没有竞争的情况下，直接通过 CAS 操作将值累加到 base 基础值上；
     * - 如果有竞争的话，会将值累加到 cells 中的某个 Cell 元素里面。
     * 因此，value = base + ∑[0~n]cells。
     */
    transient volatile Cell[] cells;

    AStriped64_AAAAA() {
    }

    // --- [核心方法，实现原理] --- //

    /**
     * 计算基础值：
     * 1. 在没有锁竞争的情况下会直接更新 base 基础值；
     * 2. 在 cells 初始化时，cells 不可用，也会尝试通过 CAS 操作值累加到 base 基础值上。
     */
    final boolean casBase(long expect, long update) {
        return UNSAFE.compareAndSwapObject(this, baseOffset, expect, update);
    }

    /**
     * 累加热点分散值，存放 Cell 单元格的哈希表，大小为 2 的幂。
     * - 如果有竞争的话，会将值累加到 cells 中的某个 Cell.value 里面。
     * 因此，value = base + ∑[0~n]cells。
     * 算法过程：
     * 1）计算当前争用线程对应的哈希值，用于定位 cells 数组中的哈希槽；
     * 2）CAS “自旋”，写入 update 更新数据：
     * - 如果 cells 数组还未完成初始化或正在扩容，将当前争用线程的 update 更新值直接累加到 base 基础值上，退出循环。
     * - 如果 cells 数组已经初始化，将当前争用线程的 update 更新数据写入到对应的 Cell 单元格中，一直到操作成功，退出循环。
     */
    final void longAccumulate(long update, LongBinaryOperator function, boolean wasUncontended) {
        // 1）计算当前争用线程对应的哈希值，用于定位 cells 数组中的哈希槽；
        int hash;
        if ((hash = getRandomProbe()) == 0) {
            ThreadLocalRandom.current();
            hash = getRandomProbe();
            wasUncontended = true;
        }
        // 扩容意向，如果最后一个插槽为非空，则为 True，可以扩容；否则为 False，不可扩容
        boolean collide = false;
        // 2）CAS “自旋”，一直到操作成功
        for (; ; ) {
            Cell[] cs;
            int n;
            Cell c;
            long expect;
            /**
             * CASE 1：表示 cells 数组已经初始化了，当前线程应该将 update 数据写入到对应的 Cell 单元格中。
             */
            if ((cs = cells) != null && (n = cs.length) > 0) {
                // CASE 1.1：对应的 Cell 单元格为 null
                if ((c = cs[(n - 1) & hash]) == null) {
                    if (cellsBusy == 0) {
                        // 1）创建 Cell 单元格
                        Cell cell = new Cell(update);
                        // 2）在 cells 数组中找个空位置，将新创建的 Cell 单元格放进去
                        if (cellsBusy == 0 && casCellsBusy()) {
                            // 2.2）寻找空位置，把 cell 放进去
                            boolean created = false;
                            try {
                                Cell[] arr;
                                int len, index;
                                if ((arr = cells) != null && (len = arr.length) > 0 && arr[index = (len - 1) & hash] == null) {
                                    arr[index] = cell;
                                    created = true;
                                }
                            } finally {
                                cellsBusy = 0;
                            }
                            // 操作成功，退出循环
                            if (created) break;
                            else {
                                // 当前线程对应的插槽位置不为 null，继续循环，一直到操作成功
                                continue;
                            }
                        }
                    }
                    collide = false;
                }
                // CASE 1.2：wasUncontended 为 false，当前线程竞争修改失败
                else if (!wasUncontended) {
                    // 重新哈希，继续循环，一直到操作成功
                    wasUncontended = true;
                }
                // CASE 1.3：当前线程重新哈希后，CAS 更新 Cell 单元格，如果更新成功，就退出循环
                else if (c.cas(expect = c.value, ((function == null) ? expect + update : function.applyAsLong(expect, update)))) {
                    break;
                }
                // CASE 1.4：线程数达到最大值，或者 cells 值已过期，调整扩容意向，继续自旋，一直到操作成功
                else if (n >= NCPU || cells != cs) collide = false;
                // CASE 1.5：设置扩容意向为 true，继续自旋，一直到操作成功
                if (!collide) collide = true;
                    // CASE 1.6：执行扩容逻辑
                else if (cellsBusy == 0 && casCellsBusy()) {
                    try {
                        if (cells == cs) {
                            Cell[] tmp = new Cell[n << 1];
                            for (int i = 0; i < n; i++) tmp[i] = cs[i];
                            cells = tmp;
                        }
                    } finally {
                        cellsBusy = 0;
                    }
                    // 继续循环，一直到操作成功
                    collide = false;
                    continue;
                }
                // 加锁失败，重置当前线程的哈希值，继续循环，一直到操作成功
                hash = advanceRandomProbe(hash);
            }
            // CASE 2：表示 cells 数组还未初始化，并且 cellsBusy 加锁成功
            else if (cellsBusy == 0 && cells == cs && casCellsBusy()) {
                // 初始化 cells 数组
                boolean init = false;
                // 创建 Cell 单元格，寻找空位置，把 Cell 放进去
                try {
                    if (cells == cs) {
                        Cell[] tmp = new Cell[2];
                        tmp[hash & 1] = new Cell(update);
                        cells = tmp;
                        init = true;
                    }
                } finally {
                    cellsBusy = 0;
                }
                // 操作成功，退出循环
                if (init) break;
            }
            /**
             * CASE 3：当前线程 cellsBusy 加锁失败，表示其他线程正在初始化 cells 数组
             * 所以，将当前线程的 update 值累加到 base 基础值上，退出循环。
             */
            else if (casBase(expect = base, ((function == null) ? expect + update : function.applyAsLong(expect, update)))) {
                break;
            }
        }
    }
}
